package cn.cxq.learning.stack;

import java.util.Stack;

/**
 * 剑指offer
 * 包含min函数的栈
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：529317
 * 本题知识点： 栈
 * 算法知识视频讲解
 * 题目描述
 * 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
 */
public class MinStack {

    Stack<Integer> minStack = new Stack<>();
    int min = Integer.MAX_VALUE; //用一个指针保存最小值

    public void push(int node) {
        if (node < min) {
            min = node;
        }
        minStack.push(node);
    }

    public void pop() {
        minStack.pop();
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < minStack.size(); i++) {
            if (minStack.get(i) < min) {
                min = minStack.get(i);
            }
        }
        this.min = min;
    }

    public int top() {
        return minStack.peek();
    }

    public int min() {
        return min;
    }

}

/**
 * 别人的双栈策略，等大小在相同位置保存每个元素的最小值，挺有意思的
 */
class MinStack2 {

    Stack<Integer> minStack = new Stack<>();
    Stack<Integer> stack = new Stack<>();

    public void push(int node) {

        stack.push(node);
        if (minStack.empty()) {
            minStack.push(node);
        } else {
            if (minStack.peek() > node) {
                minStack.push(node);
            } else {
                minStack.push(minStack.peek());
            }
        }
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

    public int top() {
        return minStack.peek();
    }

    public int min() {
        return minStack.peek();
    }

}
